package week_07;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 212. 单词搜索 II
 * 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
 * <p>
 * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
 * 同一个单元格内的字母在一个单词中不允许被重复使用。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：board = [['o','a','a','n'],['e','t','a','e'],['i','h','k','r'],['i','f','l','v']], words = ['oath','pea','eat','rain']
 * 输出：['eat','oath']
 * 示例 2：
 * <p>
 * <p>
 * 输入：board = [['a','b'],['c','d']], words = ['abcb']
 * 输出：[]
 */
public class FindWords_II_212 {
    public class TrieNode {
        String word;
        Map<Character, TrieNode> child;

        TrieNode() {
            this.word = null;
            this.child = new HashMap<>();
        }
    }

    TrieNode root = new TrieNode();
    List<String> ans = new ArrayList<>();
    int[] dx = {-1, 0, 0, 1};
    int[] dy = {0, -1, 1, 0};
    boolean[][] isVisited;
    int m;
    int n;

    public List<String> findWords(char[][] board, String[] words) {
        m = board.length;
        n = board[0].length;

        for (String word : words) {
            insertWord(word);
        }
        // 深搜dfs+字典树trie
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                isVisited = new boolean[m][n];
                isVisited[i][j] = true;
                dfs(board, i, j, root);
            }
        }
        return ans;
    }

    public void dfs(char[][] board, int x, int y, TrieNode cur) {
        char ch = board[x][y];
        TrieNode fa = cur;
        if (!fa.child.containsKey(ch)) return;
        TrieNode curr = fa.child.get(ch);
        if (curr.word != null) {
            System.out.println(curr.word);
            // 需要删除命中的跟
            ans.add(curr.word);
            curr.word = null;
        }
        if (curr.child.isEmpty()) {
            fa.child.remove(ch);
        }
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
            if (isVisited[nx][ny]) continue;
            isVisited[nx][ny] = true;
            dfs(board, nx, ny, curr);
            isVisited[nx][ny] = false;
        }
    }

    public void insertWord(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (!cur.child.containsKey(c)) {
                cur.child.put(c, new TrieNode());
            }
            cur = cur.child.get(c);
        }
        cur.word = word;
    }

    public static void main(String[] args) {
        FindWords_II_212 test = new FindWords_II_212();
//        char[][] boards = new char[][]{{'o', 'a', 'a', 'n'}, {'e', 't', 'a', 'e'}, {'i', 'h', 'k', 'r'}, {'i', 'f', 'l', 'v'}};
//        String[] words = new String[]{"oath", "pea", "eat", "rain"};
        char[][] boards = new char[][]{{'a', 'b'}};
        String[] words = new String[]{"ba"};
        test.findWords(boards, words);
    }
}
